Gerichteter Graph

Ein gerichteter Graph oder Digraph (von englisch directed graph) besteht aus

• einer Menge ${\displaystyle V}$ von Knoten (englisch vertex/vertices, oft auch Ecken genannt) und
• einer Menge geordneter Knotenpaare ${\displaystyle E\subseteq V\times V}$ von Kanten.^[1]

Die Kanten ${\displaystyle (v,w)\in E}$ eines gerichteten Graphen sind gerichtete Kanten (englisch directed edge/edges, manchmal auch Bögen). Diese werden häufig als Pfeile dargestellt und können nur in einer Richtung durchlaufen werden. Im Gegensatz dazu sind die Kanten eines ungerichteten Graphen ungeordnete Knotenpaare ${\displaystyle \{v,w\}}$. Gerichtete Graphen werden dazu benutzt, Objekte und die dazwischenliegenden Verbindungen, beispielsweise von endlichen Automaten, darzustellen.

1. ↑ Reinhard Diestel: Graphentheorie. 4. Auflage. Springer, Berlin u. a. 2010, ISBN 978-3-642-14911-5, S. 28–30 (englisch, 4. elektronische Ausgabe 2010 – Erstausgabe: 1996).